Existing Internet Protocol (IP) routers operate based on a hop-by-hop forwarding principle. The base function of this is realised in a table containing destinations or destination prefixes and corresponding next hops, i.e. outgoing interfaces. This way, each node receiving a packet data unit (PDU) is capable of searching the next-hop to which it should forward the packet. In the forwarding engine hardware, this table is often referred to as a forwarding table.
The internet is currently organised in a hierarchical manner, meaning that an intra-domain routing protocol or Interior Gateway Protocol (IGP)—typically Open Shortest Path First (OSPF), or Intermediate System to Intermediate System IS-IS—calculates the shortest paths inside a local domain, and a separate protocol takes care of inter-domain routing. This Exterior Gateway Protocol (EGP) in IP networks is typically implemented as Border Gateway Protocol (BGP). In practice, BGP identifies and returns the edge-router (i.e. the inter-domain next-hop) that should be used to reach the destination prefix. Subsequently recursive lookup is used in the router in order to find the local next-hop (i.e. the outgoing interface) leading towards this particular edge router.
IP router implementations often contain a separate forwarding table for each incoming interface, although in practice the tables are often filled with the same values. However, some recent proposals already utilise the possibility that these tables may be filled with different values (Zifei Zhong, et al.: “Failure Inferencing based Fast Rerouting for Handling Transient Link and Node Failure”, Infocom 2005.)
If a link or node goes down in the network, the appropriate routing protocols propagate this information and the router calculates a new route to the destinations. During this so-called routing re-convergence, i.e. as long as not all routers have installed the new routes (i.e. new next-hops), the network may experience transient routing loops and lost packets.
Normally, forwarding tables are recalculated in each router by a control element (the routing engine). However, in some other concepts, like in the distributed router system described in “Performance Evaluation of Control Plane Modularization and Decentralisation for BGP”, Markus Hidell et al., Usenix 2006, the forwarding tables are calculated on distributed control elements and are downloaded to the physically separate forwarding elements over the regular IP network.
Some solutions for IP-based fast re-route (IP-FRR) are based on putting alternative “virtual” IP addresses per node (also known as “not-via addresses”) into each router's forwarding table. These virtual addresses are then allocated a different next-hop than the normal IP address of the destination. This way, in case of a failure, a detour path can be used leading to the same destination.
Existing forwarding tables are nowadays very long. It has been observed by M. Hidell et al. (supra) that the number of entries can be higher than 100,000. Currently the forwarding table of a router is set up in such a way that it contains an entry for each destination or each destination prefix the router is aware of.
Using not-via addresses further increases the entries in forwarding tables. Aiming at the repair of single node or link failures, the increase is a number of additional entries equal to the number of links in the network. With double failure protection the increase is a square function of links.
The growth of forwarding tables slows down the forwarding, because the lookup from a large database takes longer than from a small one.
Calculating the routes for external prefixes takes more time than required due to the lookup of irrelevant prefixes in recursive lookup.
A major part of re-convergence time of link state routing protocols is spent with the download of the next-hops into the forwarding engines of line cards.
In the distributed router concept, a high number of destination prefixes also increases the signalling bandwidth overhead required to download the forwarding tables to the forwarding elements.